//按照先序遍历序列建立二叉树的二叉链表
//从键盘输入二叉树的节点信息，建立二叉树的存储结构
//在建立二叉树的过程中按照二叉树先序方式建立
//
//当只有一个先序序列的时候无法确定为一个一颗二叉树
//需要在先序序列中用特殊字符补充空节点，使二叉树的建立唯一



//#include<stdio.h>
//#include<stdlib.h>
//
//typedef char BTNDataType;
//typedef struct BinaryTreeNode
//{
//	BTNDataType data;
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//}BTNode;
//
//typedef struct BinaryTree
//{
//	BTNode* root;
//}BT;
//
//BTNode* BinaryTreeCreate(BTNode* root)
//{
//	char ch;
//	printf("输入一个二叉树先序序列，并且用#代表空树\n");
//	//scanf_s("%c", &ch);
//	ch = getchar();
//	if (ch=='#')
//	{
//		root = NULL;
//	}
//	else
//	{
//		root = (BTNode*)malloc(sizeof(BTNode));
//		root->data = ch;
//		root->left = BinaryTreeCreate(root->left);
//		root->right = BinaryTreeCreate(root->right);
//	}
//	return root;
//}
//void TreeCreate(BT* B1)
//{
//	B1->root = NULL;
//}
//void PrevOrder(BTNode* root)//先序遍历
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	printf("%c ", root->data);//根结点
//	PrevOrder(root->left);//左子树
//	PrevOrder(root->right);//右子树
//}
//int main()
//{
//	BT t1;
//	TreeCreate(&t1);
//	(&t1)->root = BinaryTreeCreate((&t1)->root);
//	PrevOrder((&t1)->root);
//	system("pause");
//	return 0;
//}




//方法二
//读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
//例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树
//建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果

#define _CRT_SECURE_NO_WARNINGS//忽视scanf安全性问题

#include <stdlib.h>
#include<stdio.h>

struct treeNode
{
	char val;
	struct treeNode* left;
	struct treeNode* right;
};

struct treeNode* rebulidTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	//前序构建二叉树
	struct treeNode* root = (struct treeNode*)malloc(sizeof(struct treeNode));
	root->val = str[(*pi)++];
	root->left = rebulidTree(str, pi);
	root->right = rebulidTree(str, pi);
	return root;
}

void Inorder(struct treeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Inorder(root->left);
	printf("%c ", root->val);
	Inorder(root->right);
}

int main()
{
	char str[100];
	scanf("%s", &str);
	int i = 0;
	struct treeNode* root = rebulidTree(str, &i);
	Inorder(root);
	return 0;
}